#include <iostream>
#include <string>
#include <stack>
#include <unordered_map>
using namespace std;


class Solution {
public:
    bool isValid(string s) {
        
        stack<char> st;
        unordered_map<char,char> has;
        has[']']='[',has[')']='(',has['}']='{';
        for(int i=0;i<static_cast<int>(s.size());++i){
			
			if(has.count(s[i])){
				
				if(st.empty() || has[s[i]]!=st.top()){
					
					return false;
				}
				else{
					
					st.pop();
				}
			}
			else{
				
				st.push(s[i]);
			}

		}
        
        return st.empty();
    }
};
